package sort;

public class QuickSort {

    //快速排序
    public static void quickSort(int[] arr, int low, int high) {
        //如果指针在同一个位置，退出
        if (high - low < 1) {
            return;
        }
        //标记
        boolean flag = true;
        //指针起始位置
        int start = low;
        int end = high;
        //默认中间值为低指针的第一个值
        int midValue = arr[low];
        while(true) {
            //高指针移动
            if (flag) {
                //如果列表右方的数据大于中间值，则向左移动
                if (arr[high] > arr[midValue]) {
                    high--;
                } else if (arr[high] < arr[midValue]) {
                    //如果小于，则覆盖最开始的低指针值，并移动低指针，标志位改为低指针开始移动
                    arr[low] = arr[high];
                    low++;
                    flag = false;
                }
            } else {
                //如果低指针数据小于中间值，则低指针向右移动
                if (arr[low] < arr[midValue]) {
                    low++;
                } else if (arr[low] > arr[midValue]) {
                    //如果大于，则覆盖高指针停留的数据，并向左移动高指针，切换为高指针移动
                    arr[high] = arr[low];
                    high--;
                    flag = true;
                }
            }
            //两个指针位置相同时，找到了中间位置的值，并退出循环
            if (low == high) {
                arr[low] = midValue;
                break;
            }
        }
        quickSort(arr,start,low - 1);
        quickSort(arr,low + 1, end);
    }

}
